<?php
/**
 * User: LRZ
 * Date: 2020/1/11
 * Time: 14:56
 */

/**
 *  53.最大子序和
 *
 *  标签：数组、动态规划
 *
 *  给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 *  示例:
 *      输入: [-2,1,-3,4,-1,2,1,-5,4],
 *      输出: 6
 *      解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 *
 *  进阶:
 *      如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/maximum-subarray
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
$res  = maxSubArray($nums);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function maxSubArray($nums)
{
    $maxSum = $nums[0];
    $sum    = 0;
    foreach ($nums as $k => $v) {
        if ($sum > 0) {
            $sum += $v;
        } else {
            $sum = $v;
        }
        $maxSum = max($sum, $maxSum);
    }
    return $maxSum;
}
/**
 * 循环期间的变量变化情况
 * $k = 0; $sum = -2; maxSum = -2;
 * $k = 1; $sum = 1;  maxSum = 1;
 * $k = 2; $sum = -2; maxSum = 1;
 * $k = 3; $sum = 4;  maxSum = 4;
 * $k = 4; $sum = 3;  maxSum = 4;
 * $k = 5; $sum = 5;  maxSum = 5;
 * $k = 6; $sum = 6;  maxSum = 6;
 * $k = 7; $sum = 1;  maxSum = 6;
 * $k = 8; $sum = 5;  maxSum = 6;
 */